package com.base.leetcode;

import java.util.LinkedList;

/**
 * @Author: hdhao
 * @Create: 2023/4/1 - 21:05
 * @Version: v1.0
 */
//逆波兰表达式求值
//逆波兰表达式也称后缀表达式,即运算符写在后面
    //从左向右进行计算
    //不必考虑运算符优先级,即不用考虑括号
public class Leetcode150 {

    /*
    1+2 中缀
    1,2 后缀
     */

    /**
     * 遍历字符串,
     * 遇到数字压入栈
     * 遇到运算符,就从栈中弹出两个数字做运算,将计算结果压入栈
     * 遍历结束后,栈中剩下的数字就是结果
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens){
        LinkedList<Integer> stack = new LinkedList<>();
        for (String t : tokens) {
            switch (t){
                case "+":
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a+b);
                    break;
                case "-":
                    Integer m = stack.pop();
                    Integer n = stack.pop();
                    stack.push(n-m);
                    break;
                case "*":
                    Integer x = stack.pop();
                    Integer y = stack.pop();
                    stack.push(y*x);
                    break;
                case "/":
                    Integer o = stack.pop();
                    Integer p = stack.pop();
                    stack.push(p/o);
                    break;
                default:
                    stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String[] tokens = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
        System.out.println(new Leetcode150().evalRPN(tokens));
        tokens = new String[]{"2","1","+","3","*"};
        System.out.println(new Leetcode150().evalRPN(tokens));
    }
}
